package 二叉树;

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.LinkedList;

public class JZ37序列化二叉树 {

    /**
     * 请实现两个函数，分别用来序列化和反序列化二叉树。
     *
     * 示例: 
     * 你可以将以下二叉树：
     *
     *     1
     *    / \
     *   2   3
     *      / \
     *     4   5
     *
     * 序列化为 "[1,2,3,null,null,4,5]"
     */

    public String serialize(TreeNode root) {
        if(root==null){
            return "[]";
        }
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.addLast(root);
        StringBuilder sb=new StringBuilder();
        sb.append("[");
        while (!queue.isEmpty()){

            int count=queue.size();
            boolean isLast=true;

            while (count>0){

                TreeNode treeNode = queue.removeFirst();
                sb.append(treeNode!=null?treeNode.val:null).append(",");
                if(treeNode!=null) {
                    queue.addLast(treeNode.left);
                    queue.addLast(treeNode.right);
                    if(treeNode.left!=null||treeNode.right!=null){
                        isLast=false;
                    }
                }
                count--;
            }

            if(isLast){
                break;
            }

        }

        sb.deleteCharAt(sb.length()-1);
        sb.append("]");

        return sb.toString();
    }

    public TreeNode deserialize(String data) {

        if(data.equals("[]")){
            return null;
        }

        data=data.substring(1,data.length()-1);
        String[] strArr = data.split(",");
        Integer[] arr=new Integer[strArr.length];
        for (int i = 0; i < strArr.length; i++) {
            arr[i]=(!strArr[i].equals("null")?Integer.parseInt(strArr[i]):null);
        }

        TreeNode root=new TreeNode(arr[0],null,null);
        LinkedList<TreeNode> queue=new LinkedList<>();
        queue.addLast(root);

        for (int i = 1; i < arr.length;) {

            if(queue.peekFirst()==null){
                queue.removeFirst();
                continue;
            }
            TreeNode leftNode=null;
            if(arr[i]!=null){
                leftNode=new TreeNode(arr[i]);
            }
            i++;
            TreeNode rightNode = null;
            if(arr[i]!=null) {
                rightNode = new TreeNode(arr[i]);
            }
            i++;

            TreeNode treeNode = queue.removeFirst();
            treeNode.left=leftNode;
            treeNode.right=rightNode;

            queue.addLast(leftNode);
            queue.addLast(rightNode);

        }

        return root;
    }

    public static void main(String[] args) {
        TreeNode treeNode = TreeNode.getNodeByArr(new Integer[]{1,2,3,null,null,4,5});
        treeNode.printNode();
        JZ37序列化二叉树 jz=new JZ37序列化二叉树();
        String result1 = jz.serialize(treeNode);
        System.out.println(result1);
        TreeNode result2 = jz.deserialize(result1);
        result2.printNode();
        ThreadLocal threadLocal=new ThreadLocal();
        threadLocal.set(1);
        threadLocal.get();
    }

}
